package com.zklh.leetcode.array.middle;

/**
 * 在D天送达包裹算法实现,
 *
 * @author 坐看落花
 * @version 1.0
 * @date 2021/7/30 19:38
 */
public class Solution1011 {
    public int shipWithinDays(int[] weights, int days) {

        int minPower = getMax(weights);
        int maxPower = getSum(weights);

        int left = minPower;
        int right = maxPower;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (canShip(weights, mid, days)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    /**
     * Power的每天运输能力 可以在days 天内运输完所有获取的判断
     * @param weights
     * @param power
     * @param days
     * @return
     */
    private boolean canShip(int[] weights, int power, int days) {
        int needDays = 0;
        int capacity = 0;
        for (int weight : weights) {
            // 小于 只能等下一天运输了
            if (capacity < weight) {
                needDays += 1;
                capacity = power;
            }
            capacity -= weight;
        }
        return needDays <= days;
    }

    private int getMax(int[] weights) {
        int max = 0;
        for (int weight : weights) {
            max = Math.max(weight, max);
        }
        return max;
    }

    private int getSum(int[] weights) {
        int sum = 0;
        for (int weight : weights) {
            sum += weight;
        }
        return sum;
    }

    public static void main(String[] args) {
        Solution1011 solution1011 = new Solution1011();
        System.out.println(solution1011.shipWithinDays(new int[]{1,2,3,1,1}, 4));
    }

}
